Unordered associative containers (C++)

C++ Standard Library
Standard Template Library
C standard library
Miscellaneous headers:

In computing, unordered associative containers refer to a group of class templates in the standard library of the C++ programming language that implement variations of hash table. Being templates, they can be used to store arbitrary elements, such as integers or custom classes. The following containers are defined in the current revision of the C++ standard: unordered_set, unordered_map, unordered_multiset, unordered_multimap. Each of these containers differ only on constraints placed on their elements.

The unordered associative containers are similar to the associative containers in C++ standard library but has different constraints. As their name implies, the elements in the unordered associative containers are not ordered. This is due to the use of hashing to store objects. The containers can still be iterated through like a regular associative containers.

Contents

History

The first widely used implementation of hash tables in the C++ language was hash_map, hash_set, hash_multimap, hash_multiset class templates of the SGI STL.[1]. Due to its usefulness it was later included in several other implementations of the C++ standard library, e.g. in the GCC's libstdc++[2] or in MSVC standard library.

The hash_* class templates were proposed into C++ TR1 and were accepted under names unordered_*.[3] Later, they were incorporated into the C++11 revision of the C++ standard.[4]. An implementation is also available in the Boost C++ Libraries as <boost/unordered_map.hpp>[5].

Design

Overview of functions

The containers are defined in headers named after the names of the containers, e.g. unordored_set is defined in header <unordered_set>. All containers satisfy the requirements of the Container concept, which means they have begin(), end(), size(), max_size(), empty(), and swap() methods.

unordered_set
(C++11)		 unordered_map
(C++11)		 unordered_multiset
(C++11)		 unordered_multimap
(C++11)		 Description
(constructor) (constructor) (constructor) (constructor) Constructs the container from variety of sources
(destructor) (destructor) (destructor) (destructor) Destructs the set and the contained elements
operator= operator= operator= operator= Assigns values to the container
get_allocator get_allocator get_allocator get_allocator Returns the allocator used to allocate memory for the elements
Element access N/A at N/A N/A Accesses specified element with bounds checking.
N/A operator[] N/A N/A Accesses specified element without bounds checking.
Iterators begin begin begin begin Returns an iterator to the beginning of the container
end end end end Returns an iterator to the end of the container
Capacity empty empty empty empty Checks whether the container is empty
size size size size Returns number of elements in the container.
max_size max_size max_size max_size Returns the maximum possible number of elements in the container
Modifiers clear clear clear clear Clears the contents.
insert insert insert insert Inserts elements.
emplace emplace emplace emplace Constructs elements in-place (C++11)
emplace_hint emplace_hint emplace_hint emplace_hint Constructs elements in-place using a hint (C++11)
erase erase erase erase Erases elements.
swap swap swap swap Swaps the contents with another container.
Lookup count count count count Returns the number of elements matching specific key.
find find find find Finds an element with specific key.
equal_range equal_range equal_range equal_range Returns a range of elements matching specific key.
Bucket interface ...
Hash policy ...
Observers hash_function hash_function hash_function hash_function Returns the function used to create hash of a key
key_eq key_eq key_eq key_eq Returns key comparison function.

Usage example

#include <iostream>
#include <string>
#include <unordered_map>
 
int main()
{
    std::unordered_map<std::string, int> months;
    months["january"] = 31;
    months["february"] = 28;
    months["march"] = 31;
    months["april"] = 30;
    months["may"] = 31;
    months["june"] = 30;
    months["july"] = 31;
    months["august"] = 31;
    months["september"] = 30;
    months["october"] = 31;
    months["november"] = 30;
    months["december"] = 31;
    std::cout << "september -> " << months["september"] << std::endl;
    std::cout << "april     -> " << months["april"] << std::endl;
    std::cout << "december  -> " << months["december"] << std::endl;
    std::cout << "february  -> " << months["february"] << std::endl;
    return 0;
}

References

  1. ^ "hash_map<Key, Data, HashFcn, EqualKey, Alloc>". SGI. http://www.sgi.com/tech/stl/hash_map.html. Retrieved 26 January 2011. 
  2. ^ "libstdc++: hash_map Class Template Reference". http://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.1/class____gnu__cxx_1_1hash__map.html. Retrieved 26 January 2011. 
  3. ^ WG21 (9 April 2003). "A Proposal to Add Hash Tables to the Standard Library (revision 4)". n1456. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1456.html. 
  4. ^ WG21 (21 August 2010), Working Draft, Standard for Programming Language C++, n3126, http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3126.pdf 
  5. ^ "Class template unordered_map". Boost. http://www.boost.org/doc/libs/1_45_0/doc/html/boost/unordered_map.html. Retrieved 26 January 2011.